package com.lihepeng.leecode.frequency.simulator;

import java.util.HashMap;

/**
 * 设计LRU 缓存
 * 因为要求写入 和获取都是O(1) 索引使用hash链表结构来完成
 *
 */
public class Solution100 {

    private LRUCache lruCache;
    public Solution100(int capacity) {
        lruCache = new LRUCache(capacity);
    }

    public int get(int key) {
        HashMap<Integer, Node> map = lruCache.map;
        if (!map.containsKey(key)) {
            return -1;
        }
        lruCache.makeRecently(key);
        Node node = map.get(key);
        return node.value;
        // write code here
    }

    public void set(int key, int value) {
        HashMap<Integer, Node> map = lruCache.map;
        if (map.containsKey(key)) {
            lruCache.delKey(key);
            lruCache.addRecently(key,value);
            return;
        }
        if (map.size() == lruCache.cap) {
            // 删除最长时间没有使用的元素
            lruCache.removeLeastRecently();
        }
        lruCache.addRecently(key, value);




    }

    static class LRUCache{
        private HashMap<Integer,Node> map;
        private DoubleList cache;
        private int cap;

        public LRUCache(int capacity) {
            this.cap = capacity;
            this.map = new HashMap<>();
            this.cache = new DoubleList(capacity);
        }
        public void makeRecently(int key) {
            // 将某一个key 设置成 最近使用的元素
            Node x = map.get(key);
            cache.remove(x);
            cache.addLast(x);
        }

        /**
         * 将某一个元素添加为最近使用的元素
         * @param key
         */
        public void addRecently(int key,int val){
            Node node = new Node(key, val);
            this.cache.addLast(node);
            this.map.put(key,node);
        }
        public void delKey(int key) {
            Node node = map.get(key);
            map.remove(node.key);
            cache.remove(node);
        }

        /**
         * 删除最久未使用的key
         */
        public void removeLeastRecently() {
            // 链表头部的节点就是最久未使用的
            Node node = cache.removeFirst();
            this.map.remove(node.key);
        }

    }


    static class DoubleList{
        // 长度
        private int size;
        // 收尾节点
        private Node tail,head;

        public DoubleList(int capacity) {
            this.size = 0;
            head = new Node(-1,-1);
            tail = new Node(-1,-1);
            this.head.next = tail;
            this.tail.prev = head;
        }
        public void addLast(Node x) {
            x.prev = tail.prev;
            x.next = tail;
            tail.prev.next = x;
            tail.prev = x;
            size++;
        }

        /**
         * 删除节点 因为是双向链表所以时间复杂读是o(1)
         * @param x
         */
        public void remove(Node x) {
            x.prev.next = x.next;
            x.next.prev = x.prev;
            size--;

        }

        /**
         * 删除第一个节点 并且返回该节点
         */
        public Node removeFirst(){
            if (head.next == tail) {
                // 不存在元素
                return null;
            }
            Node first =  head.next;
            remove(first);
            return first;
        }
        public int size() {
            return this.size;
        }

    }
    // 双向链表 节点
    static class Node{
        int key;
        int value;
        Node prev;
        Node next;

        public Node(int key,int value) {
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }

    }
}

